﻿// 0725decoding_string.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <stack>
#include <string>
#include <vector>
#include <sstream>

using namespace std;

/*
输入：s = "3[a]2[bc]"
输出："aaabcbc"

输入：s = "3[a2[c]]"
输出："accaccacc"

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

 */

class Solution {
public:
    stack<string>oh_stack;
    string decodeString(string s)
    {
        string oh_str = s;
        string result;
        int str_size = oh_str.size();
        for (int i=0; i < str_size; i++)
        {
            char oh_char = oh_str[i];
            string curr_str;
            if (oh_char==']')
            {
                string single_str;
                while (!oh_stack.empty() && ("[" != oh_stack.top()))
                {
                    single_str += oh_stack.top();
                    oh_stack.pop();
                }

                reverse(single_str.begin(), single_str.end());

                //弹出左括号
                oh_stack.pop();
                //弹出数字
                //cout << oh_stack.top();
                int count = stoi(oh_stack.top());
                oh_stack.pop();

                //cout << "count: " << count;

                while (count--)
                {
                    curr_str += single_str;
                }

                result += curr_str;

            }
            else if (oh_char>='0'&&oh_char<='9')
            {
                long curr_val = oh_str[i] - '0';
                while (i + 1 < str_size && oh_str[i + 1] >= '0' && oh_str[i + 1] <= '9')
                {
                    curr_val = curr_val * 10 + (oh_str[i+1] - '0');
                    i++;
                }
                oh_stack.push(to_string(curr_val));
            }
            else
            {
                // 注意，char转string不可以使用to_string
                // to_string是专门为int类型准备的
                string temp_str;
                temp_str += oh_char;
                oh_stack.push(temp_str);
            }
        }

        return result;
    }
};

int main()
{
    Solution solution;
    string str = "3[a2[c]]";
    cout << solution.decodeString(str);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
